package demo1;


import java.util.ArrayList;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }
}


public class Solution {

    TreeNode prev = null;
    TreeNode root = null;

    public TreeNode Convert1(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }
        Convert1(pRootOfTree.left);
        if (root == null) {
            root = pRootOfTree;
        }
        if (prev != null) {
            pRootOfTree.left = prev;
            prev.right = pRootOfTree;
        }
        prev = pRootOfTree;
        Convert1(pRootOfTree.right);
        return root;
    }


    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }
        ArrayList<TreeNode> list = new ArrayList<>();
        inorder(root, list);
        for (int i = 1; i < list.size() - 1; i++) {
            TreeNode cur = list.get(i);
            cur.left = list.get(i - 1);
            cur.right = list.get(i + 1);
        }
        list.get(0).right = list.get(1);
        list.get(list.size() - 1).left = list.get(list.size() - 2);
        return list.get(0);
    }

    private void inorder(TreeNode root, ArrayList<TreeNode> list) {
        if (root == null) {
            return;
        }
        inorder(root.left, list);
        list.add(root);
        inorder(root.right, list);
    }
}